package mo.daliy;

import java.util.Arrays;

public class L3213 {

    private static class TrieNode {
        private TrieNode[] childs = new TrieNode[26];
        private int cost = -1;
    }

    private TrieNode root = new TrieNode();

    private int[] memo;

    public int minimumCost(String target, String[] words, int[] costs) {
        // 构造前缀树

        for (int j = 0; j < words.length; j++) {
            TrieNode cur = root;
            String word = words[j];
            for (int i = 0; i < word.length(); i++) {
                if (cur.childs[word.charAt(i)-'a'] == null) {
                    cur.childs[word.charAt(i)-'a'] = new TrieNode();
                }
                cur = cur.childs[word.charAt(i)-'a'];
            }
            if (cur.cost == -1) {
                cur.cost = costs[j];
            } else {
                cur.cost = Math.min(cur.cost, costs[j]);
            }

        }
        // dp记忆
        memo = new int[target.length()];
        Arrays.fill(memo, -1);
        // 递归
        int ret = dfs(target, 0);
        if (ret == Integer.MAX_VALUE / 2) {
            return -1;
        }
        return ret;
    }


    private int dfs(String target, int cur) {
        if (cur == target.length()) {
            return 0;
        }
        if (memo[cur] != -1) {
            return memo[cur];
        }

        int ans = Integer.MAX_VALUE / 2;
        TrieNode node = root;
        for (int i = cur; i < target.length(); i++) {
            if (node.childs[target.charAt(i)-'a'] == null) {
                break;
            }
            node = node.childs[target.charAt(i)-'a'];
            if (node.cost != -1) {
                ans = Math.min(ans, node.cost + dfs(target, i+1));
            }
        }
        memo[cur] = ans;
        return ans;
    }

}
